1. Field of the Invention
The present invention relates to garbage collection (GC) in a memory used by an application program (AP).
2. Background of the Related Art
In some conventional object oriented programming languages, freeing of memory area corresponding to objects (also called “object instance”) that are no longer required after being used by an AP is the responsibility of the execution environment. Employing such a method relieves the creator of the AP from being concerned with allocation and freeing of memory area. One example of an object oriented programming language is Java. Note that Java is a trademark of the Sun Microsystems Inc., of the USA.
An AP written using such a language is run on an execution environment that includes a garbage collection (GC) mechanism that automatically frees the memory area corresponding to objects that are no longer required.
When an AP is being executed, the GC configuration detects that a memory area corresponding to a dynamically-allocated object is not being referenced from anywhere, and frees the memory area so that the memory area is in a reusable state.
In a multithreaded AP, each thread corresponds to a stack area, and, in an operation process, stores data in the stack area, refers to stored data, and generates an object. Ordinarily when an object is generated, a pointer for the object (hereinafter called an “object pointer”) is stored in the stack area. The object pointer is data indicating the location of the object in the memory. The object is accessed from the thread by referring to the object pointer. Furthermore, ordinarily, an object pointer to another object is also stored in the object.
All objects that are being referenced by the AP at a particular point in time can be reached either directly from an object pointer included in one of the stack areas corresponding to the threads, or via the object pointers in one or more objects.
In response to this, the GC mechanism essentially determines that a memory area corresponding to an object that is no longer reachable from an object pointer in a stack at a particular point in time is no longer required, and frees the memory area.
One conventional GC method is mark-and-sweep. The mark-and-sweep method marks all objects that can be reached from an object pointer, then scans all objects, and frees memory area corresponding to objects that are not marked.
When this mark-and-sweep GC is performed during the execution of a multithreaded AP, priority may be given to prompt performance of GC. To do so, marking of all objects that can be reached from an object pointer in the stack corresponding to each thread is performed after simply stopping all threads. Then the stop on all the threads is released, and objects that are not marked are freed. However, the following problem occurs in such a case.
Specifically, there is a possibility that all the threads of the AP will be stopped for a relatively long time. During this time, the computer does not react to user operations or the like, and, as one example, the display contents on the display of the computer may remain the same. This causes confusion for the user.
One method for solving this problem is disclosed in Japanese Patent No. 3027845. This method proposes GC using mark-and-sweep that is executed without stopping a multithreaded AP at all.
With this method, first processing is performed for marking all objects that can be reached from an object that is a root node and all objects that can be reached from object pointers in the stack area for each thread. Second processing is then performed, when an object pointer to an object has moved due to an operation of a thread of an AP (hereinafter called an, “AP thread”) during the first processing, and is for stacking data expressing that object in a mark stack area, and when the marking processing is complete, further marking all objects that can be reached from the mark stack. Finally, memory areas corresponding to unmarked objects are freed.
However, with this method that marks without stopping the AP, there is a possibility that, since data in the stack area changes due to AP thread operation, part of the processing for marking objects that can be reached from the object pointer in the stack area will be wasteful.
Take, for example, the following case. While a thread for garbage collecting is executing processing (here, called “processing A”) for detecting an object pointer (here, called “object pointer A”) in one stack area of the AP and marking objects that are reachable from the object pointer A, the AP thread corresponding to the stack area copies the object pointer A or the one or more object pointers in the objects, and newly stores the copied object pointer A or object pointers in a stack area. Here, the thread that performs GC will, after ending the processing A, either perform processing that duplicates the processing A in part, or perform check processing to prevent duplicate processing. Either processing will be wasteful. This wasteful processing leads to an unnecessary increase in the CPU time required from start to completion of GC, and consequently lowers the usage efficiency of the CPU.